This invention relates to software for managing a database of records on a computer and, in particular, software for allowing large databases to be updated with new records while preserving the ordered structure of the database and without the rewriting of the database or significant sacrifices in the speed of record retrievals.